package com.hanlin.day06;

import com.hanlin.type.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 描述：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
 * 二叉树的最大深度
 * 给定一个二叉树，找出其最大深度。
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * @author:hl.yuan
 * @date:2022-07-21
 */
public class MaxBTree {

    /**
     * 二叉树的最大深度
     * https://leetcode.cn/problems/maximum-depth-of-binary-tree/
     *
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Integer.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
     * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     * (二叉树遍历)
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 弹出
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }


    public static void main(String[] args) {
        Integer count = 100000;
        Long start;
        Long end;
        ArrayList arrayList = new ArrayList();
        start = System.currentTimeMillis();
        for (Integer i = 0; i < count; i++) {
            arrayList.add(0, i);
        }
        end = System.currentTimeMillis();
        System.out.println(end - start);
        LinkedList linkedList = new LinkedList();
        start = System.currentTimeMillis();
        for (Integer i = 0; i < count; i++) {
            linkedList.add(0, i);
        }
        end = System.currentTimeMillis();
        System.out.println(end - start);


    }


    /**
     * 二叉树先序遍历
     */
    public static void prefaceFor(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node);
        prefaceFor(node.left);
        prefaceFor(node.right);
    }

    /**
     * 二叉树中序遍历
     */
    public static void inFor(TreeNode node) {
        if (node == null) {
            return;
        }
        inFor(node.left);
        System.out.println(node);
        inFor(node.right);
    }


    /**
     * 二叉树后序遍历
     */
    public static void afterFor(TreeNode node) {
        if (node == null) {
            return;
        }
        afterFor(node.left);
        afterFor(node.right);
        System.out.println(node);
    }
}
